# -*- coding: utf-8 -*-
# @Author: shj
# @Date: 2019-03-22 11:24:21
# @LastEditTime: 2020-04-10 11:07:25
# @LastEditors: shj
# @Description: 选择排序算法
# @FilePath: /python3/algorithms/SelectionSort.py
#
"""
选择排序算法

简单选择排序的基本思想：第1趟，在待排序记录r[1]~r[n]中选出
最小的记录，将它与r[1]交换；第2趟，在待排序记录r[2]~r[n]中选出
最小的记录，将它与r[2]交换；以此类推，第i趟在待排序记录r[i]~r[n]
中选出最小的记录，将它与r[i]交换，使有序序列不断增长直到全部排
序完毕。

最坏时间复杂度	О(n²)
最优时间复杂度	О(n²)
平均时间复杂度	О(n²)
最坏空间复杂度	О(n) total, O(1) auxiliary
"""


def get_in():
    """get number for sorting"""
    nosort_list = [12, 3, 34, 56, 21, 55, 4, 7, 51]
    return nosort_list


def select_sort(nosort_list):
    '''sort the nosort list by sequence'''
    r = nosort_list[:]
    for i in range(len(nosort_list)):
        for j in range(i + 1, len(nosort_list)):
            (r[i], r[j]) = (r[i], r[j]) if r[i] < r[j] else (r[j], r[i])
    return r


def main():
    nosort_list = get_in()
    sorted_list = select_sort(nosort_list)
    print(f'the nosort_list = {nosort_list}\nthe sorted_list = {sorted_list}')


if __name__ == "__main__":
    main()